package com.example.leetcode.滑动窗口;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 找到字符串中所有字母异位词
 */
public class FindAnagrams {

    public static void main(String[] args) {
        String s = "cbaebabacd", p = "abc";

        List<Integer> anagrams = findAnagrams(s, p);
        System.out.println();
    }




    public static List<Integer> findAnagram2(String s, String p) {
        List<Integer> result = new ArrayList<>();
        // 记录s的字符次数
        int[] recordS = new int[26];
        // 记录p的字符次数
        int[] recordP = new int[26];

        // 记录p的字符次数
        for (char c : p.toCharArray()) {
            recordP[c - 'a']++;
        }

        for (int right = 0; right < s.length(); right++) {
            // 记录s字符次数
            recordS[s.charAt(right) - 'a']++;
            // 获取窗口左边界，p的长度就是窗口
            int left = right - p.length() + 1;
            // 窗口长度未达到p的长度
            if (left < 0) {
                continue;
            }
            // 找到字符串中所有字母异位词
            if (Arrays.equals(recordS, recordP)) {
                result.add(left);
            }
            // 窗口左边界离开
            recordS[s.charAt(left) - 'a']--;
        }

        return result;
    }


    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int[] cntP = new int[26]; // 记录 p 的每种字母的出现次数
        int[] cntS = new int[26]; // 记录 s 的长为 p.length() 的子串 s' 的每种字母的出现次数

        // 记录 p 的字母
        for (char c : p.toCharArray()) {
            cntP[c - 'a']++;
        }
        for (int right = 0; right < s.length(); right++) {
            cntS[s.charAt(right) - 'a']++; // 右端点字母进入窗口
            // 窗口左边界。p的长度作为窗口的长度
            int left = right - p.length() + 1;
            // 窗口长度不足 p.length()
            if (left < 0) {
                continue;
            }
            // s' 和 p 的每种字母的出现次数都相同，找到字符串中所有字母异位词
            if (Arrays.equals(cntS, cntP)) {
                ans.add(left); // s' 左端点下标加入答案
            }
            cntS[s.charAt(left) - 'a']--; // 左端点字母离开窗口
        }
        return ans;
    }


}
